package leetcode.editor.cn.dsa08_hashtable;
//给定一个正整数数组 A，如果 A 的某个子数组中不同整数的个数恰好为 K，则称 A 的这个连续、不一定独立的子数组为好子数组。
//
// （例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。） 
//
// 返回 A 中好子数组的数目。 
//
//
// 示例 1： 
// 输入：A = [1,2,1,2,3], K = 2
//输出：7
//解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
// 
//
// 示例 2： 
// 输入：A = [1,2,1,3,4], K = 3
//输出：3
//解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].
// 
//
// 提示： 
// 1 <= A.length <= 20000
// 1 <= A[i] <= A.length 
// 1 <= K <= A.length 
// 
// Related Topics 哈希表 双指针 Sliding Window 
// 👍 125 👎 0

import java.util.HashMap;
import java.util.Map;

public class SubarraysWithKDifferentIntegers992 {
    public static void main(String[] args) {
        Solution solution =
                new SubarraysWithKDifferentIntegers992().new Solution();
        //int[] arr = {1,2,1,2,3}; int k = 2; //7
        //int[] arr = {1,2,1,3,4}; int k = 3; //3
        //int[] arr = {2,1,2,1,1}; int k = 3; //0
        //int[] arr = {2,2,1,2,2,2,1,1}; int k = 2; //23
        int[] arr = {1,2}; int k = 1; //2
        System.out.println(solution.subarraysWithKDistinct(arr, k));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int subarraysWithKDistinct(int[] A, int K) {
            int count = 0, left = 0, right = 0;
            int len = A.length;
            // 使用map映射存储每个数字与数字出现次数
            Map<Integer, Integer> map = new HashMap<>();
            // 循环退出条件即右指针移动到结尾，并且此时含不同整数的个数小于K
            // 如果等于K，说明左指针还有移动的空间
            // 需要继续移动左指针直到含有的不同整数的个数不满足条件
            while (right < len || map.size() == K) {
                if (map.size() == K) {
                    // 符合条件，次数+1
                    count++;
                    // 如果后面只有重复元素，则count+1
                    // 例如12符合条件时，121肯定符合，1212同理
                    for (int i = right; i < A.length; i++) {
                        if (map.containsKey(A[i])) {
                            count++;
                        } else {
                            break;
                        }
                    }
                    // 左指针移动，删除左指针元素
                    Integer val = map.get(A[left]);
                    if (val > 1) {
                        map.put(A[left], val - 1);
                    } else {
                        map.remove(A[left]);
                    }
                    left++;
                } else {
                    // 个数不符合条件，右指针移动，保存当前元素到map中
                    int num = A[right++];
                    map.put(num, map.getOrDefault(num, 0) + 1);
                }
            }
            return count;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}